#!/usr/bin/env python3

"""
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2
"""

class Solution:
    def is_interleaving(self, s1, s2, s3):
        m = len(s1)
        n = len(s2)
        if m + n != len(s3):
            return False
        m += 1
        n += 1
        dp = [[ 0 for index_n in range(n) ] for index_m in range(m)]
        dp[0][0] = 1
        for index_m in range(m):
            row = dp[index_m]
            last_row = dp[index_m - 1] if index_m >= 1 else None
            for index_n in range(n):
                if index_m == 0 and index_n == 0:
                    continue
                left = row[index_n - 1] if index_n > 0 else 1
                top = last_row[index_n] if last_row else 1
                
                s1_ch = s1[index_m - 1] if index_m > 0 else None
                s2_ch = s2[index_n - 1] if index_n > 0 else None
                current_ch = s3[index_m + index_n - 1]

                if left == 1 and s2_ch == current_ch:
                    row[index_n] = 1
                if top == 1 and s1_ch == current_ch:
                    row[index_n] = 1

        return dp[-1][-1] == 1
    
                
if __name__ == '__main__':
    s = Solution()
    assert s.is_interleaving('aabcc', 'dbbca', 'aadbbcbcac')
    assert not s.is_interleaving('aabcc', 'dbbca', 'aadbbaccc')
